package cn.orange.ch05_stack;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * LC503.下一个更大元素 II
 */
public class LC503 {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        LinkedList<Integer> stk = new LinkedList<>();
        for (int i = 0; i < 2 * n; i++) {
            int num = nums[i % n];
            while (!stk.isEmpty() && num > nums[stk.peek()]) {
                Integer pop = stk.pop();
                ans[pop] = num;
            }
            stk.push(i % n);
        }
        return ans;
    }
    public static void main(String[] args) {
        LC503 alg = new LC503();
        System.out.println(Arrays.toString(alg.nextGreaterElements(new int[]{1, 2, 1})));
        System.out.println(Arrays.toString(alg.nextGreaterElements(new int[]{1, 2, 3, 4, 3})));
    }
}
